function longestPalindromeSubseq(s){
    // 动态规划
    // f(n) = f(n-1)
   
    let len = s.length
    let dp = new Array(len)
    for(let i=0; i<len; i++){
        dp[i] = new Array()
        for(let j=0; j<len; j++){
            dp[i][j] = 0
        }
    }
    
    for(let i=len-1; i>=0; i--){
        dp[i][i] = 1
        for(let j=i; j<len; j++ ){
            
            if(i >=0 && j<len && i+1<len && j-1>=0 && i < j){
                if(s[i] === s[j]){
                    dp[i][j] = dp[i+1][j-1] + 2
                }else{
                    dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1])
                }
            }
           
        }
    }
   return dp[0][len -1]

}


let s = "bbbab"
longestPalindromeSubseq(s)
//4